import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-02-11
 * Time: 15:52
 */
//      思路：
    //       实现逆置有两种方法，一是利用栈存储链表的节点值，最后把弹出的节点值放入数组
    //            二是利用递归来实现逆序输入节点值到Arraylist，最后再将动态数组的值放到数组里面
class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
  }
public class Solution {
    ArrayList<Integer> arrayList=new ArrayList<>();
    public int[] reversePrint(ListNode head) {
        //法一：利用栈先进后出的特性来解决问题，遍历链表，将链表节点值放入栈，然后依次获取栈顶元素放入数组，再弹出栈顶元素，这样循环
//        if(head == null){
//            return null;
//        }
//        Stack<Integer> stack = new Stack<Integer>();
//        while(head!=null){
//            stack.push(head.val);
//            head = head.next;
//        }
//        int[] node_val=new int[stack.size()];
//        int len = stack.size();
//        for(int i=0;i < len; i++){
//            node_val[i] = stack.peek();
//            stack.pop();
//        }
//        return node_val;
        //法二：递归
//        int[] node_val=new int[arrayList.size()];
//        for(int i=0;i<arrayList.size(); i++){
//            node_val[i] = arrayList.get(i);
//        }
//        return node_val;

        //法三：开辟两个数组，一个数组存放正序遍历的结果，另一个数组从这个数组的后面开始放入
        int[] arr=new int[10001];
        int size=0;
        while(head != null){
            arr[size++] = head.val;//简化了循环遍历数组，可以通过个数的++来实现下标++
            head=head.next;
        }
        int[] newArr=new int[arr.length];
        int j=0;//遍历新数组
        for(int i=size - 1; i >= 0; i--){//原数组下标是从size-1开始的
            newArr[j]=arr[i];//原数组从后面开始遍历，新数组从前面开始被赋值元素
            j++;
        }
        return newArr;
    }
    //用于法二：
    /*public void reversePrinthelper(ListNode head) {
        if(head == null)
            return;
        reversePrinthelper(head.next);
        arrayList.add(head.val);
    }*/

}
